108. 将有序数组转换为二叉搜索树
#leetcode#二叉树#平衡二叉树 2025-01-31

Problem: 108. 将有序数组转换为二叉搜索树

解析

学过数据结构应该会构建有序数组二分查找的查找树，显然这是平衡二叉树

递归写法

使用递归的方法，每次取中间值作为根节点，然后递归的构建左右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//! n,log(n)->时间复杂度数组中每个元素只访问一次;空间复杂度层层二分，是log(n)
class Solution {
 public:
  TreeNode *sortedArrayToBST(vector<int> &nums) {
    return dfsBuildTree(nums, 0, nums.size() - 1);
  }
  TreeNode *dfsBuildTree(vector<int> &nums, int left, int right) {
    if(left>right){
      return nullptr;
    }
    int mid = (right - left) / 2 + left;  // 防止加法溢出
    TreeNode *node = new TreeNode(nums[mid]);
    node->left = dfsBuildTree(nums, left, mid-1);
    node->right = dfsBuildTree(nums, mid + 1, right);
    return node;
  }
};